/*https://leetcode.cn/problems/count-numbers-with-unique-digits/description/
357.统计各位数字都不同的数字个数
medium, 方钊堉 2024.10.07
数位DP*/

class Solution {
public:
    int countNumbersWithUniqueDigits(int maxDigits) {
        if (maxDigits == 0) return 1;
        if (maxDigits == 1) return 10;

        vector<int> uniqueCounts(maxDigits + 1); // 存储最多有i位数字的唯一数字数量
        uniqueCounts[0] = 1; // 0位数字只有1种情况，即空数字
        uniqueCounts[1] = 10; // 1位数字有10种情况，即0到9

        for (int digitCount = 2; digitCount <= maxDigits; digitCount++) {
            int currentCount = 1;
            for (int availableChoices = 9; availableChoices >= 9 - digitCount + 2; availableChoices--) {
                currentCount = currentCount * availableChoices;
            }
            uniqueCounts[digitCount] = uniqueCounts[digitCount - 1] + 9 * currentCount;
        }

        return uniqueCounts[maxDigits];
    }
};